package com.cqs.leetcode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Created by cqs on 2018/5/5.
 */
public class MinimumAbsoluteDifferenceBST {


    //后续
    private int lastTraversal(TreeNode node) {
        if (node != null) {
            int i = lastTraversal(node.left) ;
            int i1 = lastTraversal(node.right);
            return Math.min(Math.abs(node.val - i), Math.abs(node.val - i1));
        }
        return 0;
    }


    //非递归中根遍历
    public int getMinimumDifference(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        int pre = Integer.MAX_VALUE;
        int min = Integer.MAX_VALUE;
        do {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                node = stack.pop();
                min = Math.min(Math.abs(pre - node.val), min);
                pre = node.val;
                node = node.right;
            }
        } while (node != null || !stack.isEmpty());
        return min;
    }

    public int getMinimumDifference3(TreeNode root) {
        //中根遍历
        List<Integer> list = new ArrayList<>();
        traversal(root, list);
        return getMin(list);
    }

    private int getMin(List<Integer> list) {
        int min = Math.abs(list.get(0) - list.get(1));
        for (int i = 1; i < list.size() - 1; i++) {
            min = Math.min(min, Math.abs(list.get(i) - list.get(i + 1)));
        }
        return min;
    }

    //中根遍历二叉树
    public void traversal(TreeNode root, List<Integer> list) {
        if (root != null) {
            traversal(root.left, list);
            list.add(root.val);
            traversal(root.right, list);
        }
    }


}
